//
// Created by Administrator on 2021/4/9.
//
/*给定一个二叉树，返回所有从根节点到叶子节点的路径。

说明:叶子节点是指没有子节点的节点。

示例:

输入:

1
/   \
2     3
\
  5

输出: ["1->2->5", "1->3"]

解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-paths
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/


#include <string>
#include <vector>
#include <iostream>
#include <queue>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
};

class Solution {
private:
    vector<string> ans;
public:
    vector<string> binaryTreePaths(TreeNode *root) {
//        if (root == nullptr) return ans;
        string s;
        buildPath(root, s);
//        buildPath(root->right, s);
        return ans;
    }

    void buildPath(TreeNode *root, string s) {
        if (root == nullptr) return;
        if (!s.empty()) {
            s += "->";
        }
        s += to_string(root->val);
        if (root->left == nullptr and root->right == nullptr) {
            ans.push_back(s);
            return;
        }
        buildPath(root->left, s);
        buildPath(root->right, s);
    }
}; //AC
class Solution2 { // 题解 dfs
public:
    void construct_paths(TreeNode *root, string path, vector<string> &paths) {
        if (root != nullptr) {
            path += to_string(root->val);
            if (root->left == nullptr && root->right == nullptr) {  // 当前节点是叶子节点
                paths.push_back(path);                              // 把路径加入到答案中
            } else {
                path += "->";  // 当前节点不是叶子节点，继续递归遍历
                construct_paths(root->left, path, paths);
                construct_paths(root->right, path, paths);
            }
        }
    }

    vector<string> binaryTreePaths(TreeNode *root) {
        vector<string> paths;
        construct_paths(root, "", paths);
        return paths;
    }
};

class Solution3 { // 题解 bfs
public:
    vector<string> binaryTreePaths(TreeNode *root) {
        vector<string> paths;
        if (root == nullptr) {
            return paths;
        }
        queue<TreeNode *> node_queue;
        queue<string> path_queue;

        node_queue.push(root);
        path_queue.push(to_string(root->val));

        while (!node_queue.empty()) {
            TreeNode *node = node_queue.front();
            string path = path_queue.front();
            node_queue.pop();
            path_queue.pop();

            if (node->left == nullptr && node->right == nullptr) { // 叶节点
                paths.push_back(path);
            } else {
                if (node->left != nullptr) {
                    node_queue.push(node->left);
                    path_queue.push(path + "->" + to_string(node->left->val));
                }

                if (node->right != nullptr) {
                    node_queue.push(node->right);
                    path_queue.push(path + "->" + to_string(node->right->val));
                }
            }
        }
        return paths;
    }
};

int main() {
    auto t4 = TreeNode(5);
    auto t3 = TreeNode(3);
    auto t2 = TreeNode(2, nullptr, &t4);
    auto t1 = TreeNode(1, &t2, &t3);
    Solution sol;
    vector<string> v;
    v = sol.binaryTreePaths(&t1);
    for (const auto &x:v) cout << x << endl;
    return 0;
}